import java.util.*;

public class Solution {

    //
    public int[] getStrongest(int[] arr, int k) {
        int[] ans = new int[k];
        Arrays.sort(arr);
        int left = 0, right = arr.length - 1;
        int x = arr[(arr.length - 1) / 2];

        while(k-- > 0){
            if(x - arr[left] <= arr[right] - x){
                ans[k] = arr[right--];
            }else{
                ans[k] = arr[left++];
            }
        }
        return ans;
    }

    //
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while(left < right){
            if(numbers[left] + numbers[right] > target){
                right--;
            }else if(numbers[left] + numbers[right] < target){
                left++;
            }else{
                return new int[]{left + 1, right + 1};
            }
        }
        return new int[]{-1, -1};
    }

    //
    public boolean judgeSquareSum(int c) {
        long left = 0, right = (long) Math.sqrt(c);

        while(left <= right){
            long sum = left * left + right * right;
            if(sum > c){
                right--;
            }else if(sum < c){
                left++;
            }else{
                return true;
            }
        }
        return false;
    }

    public boolean judgeSquareSum2(int c) {
        for(int l = 0; l * l <= c / 2; l++){
            int r = (int) Math.sqrt(c - l * l);
            if(l * l + r * r == c){
                return true;
            }
        }
        return false;
    }

    //
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);

        int l = 0, r = nums.size() - 1, t = 0;
        while(l < r){
            int x = nums.get(l) + nums.get(r);
            if(x < target){
                t += r - l;
                l++;
            }else{
                r--;
            }
        }
        return t;
    }

    //
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);

        long ans = 0;
        for(int i = 0; i < nums.length; i++){
            int r = lowerBound(nums, i, upper - nums[i] + 1);
            int l = lowerBound(nums, i, lower - nums[i]);
            ans += r - l;
        }
        return ans;
    }
    private int lowerBound(int[] nums, int right, int target){
        int left = -1;

        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target){
                right = mid;
            }else{
                left = mid;
            }
        }
        return right;
    }

    public long countFairPairs2(int[] nums, int lower, int upper) {
        Arrays.sort(nums);

        long ans = 0;
        int l = nums.length, r = nums.length;
        for(int i = 0; i < nums.length; i++){
            while(r > 0 && nums[r - 1] > upper - nums[i]){
                r--;
            }
            while(l > 0 && nums[l - 1] >= lower - nums[i]){
                l--;
            }
            ans += Math.min(r, i) - Math.min(l, i);
        }
        return ans;
    }

    public long countFairPairs3(int[] nums, int lower, int upper) {
        Arrays.sort(nums);

        return count(nums, upper) - count(nums, lower - 1);
    }
    private long count(int[] nums, int upper){
        long ans = 0;
        for(int l = 0, r = nums.length - 1; l < nums.length; l++){
            while(r > l && nums[r] > upper - nums[l]){
                r--;
            }
            if(l == r){
                break;
            }
            ans += r - l;
        }
        return ans;
    }

    public long countFairPairs4(int[] nums, int lower, int upper) {
        Arrays.sort(nums);

        return count(nums, upper) - count(nums, lower - 1);
    }

    private long count2(int[] nums, int upper){
        long ans = 0;
        int l = 0, r = nums.length -1;
        while(l < r){
            if(nums[l] + nums[r] <= upper){
                ans += r - l;
                l++;
            }else{
                r--;
            }
        }
        return ans;
    }
}
